#include <iostream>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

// 定义棋盘大小
const int GRIDSIZE = 8;

// 存储决策开始时间
std::clock_t start_time;

// 设定计算机玩家最大搜索时间
int max_time = 950;

// 无穷大
constexpr static const int INF_MAX = 0x3f3f3f3f;

// 8个方向的增量
constexpr static const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
constexpr static const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 在不同局面进行程度下，各种估值的参数。
constexpr static const double f1[60] = {64.0000, 66.0000, 68.0000, 70.0000, 72.0000, 74.0000,
                                        76.0000, 78.0000, 80.0000, 82.0000, 84.0000, 86.0000,
                                        88.0000, 90.0000, 92.0000, 94.0000, 96.0000, 98.0000,
                                        100.0000, 102.0000, 104.0000, 106.0000, 108.0000, 110.0000,
                                        112.0000, 114.0000, 116.0000, 118.0000, 120.0000, 122.0000,
                                        5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000,
                                        5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000,
                                        5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000,
                                        5.0000, 5.0000, 5.0000, 5.0000, 5.0000, 5.0000};
constexpr static const double f2[60] = {32.0000, 31.1000, 30.2000, 29.3000, 28.4000, 27.5000, 26.6000,
                                        25.7000, 24.8000, 23.9000, 23.0000, 22.1000, 21.2000, 20.3000,
                                        19.4000, 18.5000, 17.6000, 16.7000, 15.8000, 14.9000, 14.0000,
                                        13.1000, 12.2000, 11.3000, 10.4000, 9.5000, 8.6000, 7.7000,
                                        6.8000, 5.9000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000};
constexpr static const double f3[60] = {32.0000, 31.1000, 30.2000, 29.3000, 28.4000, 27.5000, 26.6000,
                                        25.7000, 24.8000, 23.9000, 23.0000, 22.1000, 21.2000, 20.3000,
                                        19.4000, 18.5000, 17.6000, 16.7000, 15.8000, 14.9000, 14.0000,
                                        13.1000, 12.2000, 11.3000, 10.4000, 9.5000, 8.6000, 7.7000,
                                        6.8000, 5.9000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000};
constexpr static const double f4[60] = {64.0000, 62.0000, 60.0000, 58.0000, 56.0000, 54.0000, 52.0000,
                                        50.0000, 48.0000, 46.0000, 44.0000, 42.0000, 40.0000, 38.0000,
                                        36.0000, 34.0000, 32.0000, 30.0000, 28.0000, 26.0000, 24.0000,
                                        22.0000, 20.0000, 18.0000, 16.0000, 14.0000, 12.0000, 10.0000,
                                        8.0000, 6.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000};
constexpr static const double f5[60] = {16.0000, 15.5500, 15.1000, 14.6500, 14.2000, 13.7500, 13.3000,
                                        12.8500, 12.4000, 11.9500, 11.5000, 11.0500, 10.6000, 10.1500,
                                        9.7000, 9.2500, 8.8000, 8.3500, 7.9000, 7.4500, 7.0000, 6.5500,
                                        6.1000, 5.6500, 5.2000, 4.7500, 4.3000, 3.8500, 3.4000, 2.9500,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
                                        0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000};

// 当前是第几回合
int turnID;

// 棋子的类型
enum class Type {
    empty = 0,      /**< 空位 */
    black = 1,      /**< 黑子或黑方 */
    white = -1,     /**< 白子或白方 */
    obstacle = 2    /**< 障碍物 */
};

// 反转棋子颜色
inline void reverseType(Type &type) {
    type = type == Type::black ? Type::white : Type::black;
}

inline Type reverseAType(Type type) {
    if (type == Type::black) {
        type = Type::white;
    } else {
        type = Type::black;
    }
    return type;
}

// 棋子坐标，可以通过两种方式生成
struct Coordinate {
    int x, y;

    Coordinate() : x(0), y(0) {}

    Coordinate(int x, int y) : x(x), y(y) {}
};

// 一步棋的信息
struct Move {
    int startX, startY;         /**< 起点坐标 */
    int endX, endY;             /**< 终点坐标 */
    int obstacleX, obstacleY;   /**< 障碍物坐标 */

    // 输入一步棋
    void input() {
        cin >> startX >> startY >> endX >> endY >> obstacleX >> obstacleY;
    }

    // 输出一步棋
    void print() const {
        cout << startX << " " << startY << " " << endX << " " << endY << " " << obstacleX << " " << obstacleY << endl;
    }

    int value;
};


class AmazonsBoard {
public:
    /**
     * 初始化棋盘，放好棋子
     */
    AmazonsBoard() {
        memset(board, (int) Type::empty, sizeof(board));
        board[0][2] = board[2][0] = board[5][0] = board[7][2] = Type::black;
        board[0][5] = board[2][7] = board[5][7] = board[7][5] = Type::white;
        gridSize = GRIDSIZE;
    }

    Type &at(int x, int y) {
        return board[x][y];
    }

    /**
     * 下一步棋
     * @param move 落子&障碍坐标
     * @param currColor 当前执子颜色
     * @return 走子是否合法
     */
    bool makeAMove(Move move) {
        if (!checkMove(move)) return false;
        board[move.endX][move.endY] = board[move.startX][move.startY];
        board[move.startX][move.startY] = Type::empty;
        board[move.obstacleX][move.obstacleY] = Type::obstacle;
        return true;
    }

    /**
     * 下一步棋（另一种形式）
     * @param move 落子&障碍坐标
     * @param type 当前执子颜色
     */
    void makeMove(Move move, Type type) {
        board[move.endX][move.endY] = type;
        board[move.startX][move.startY] = Type::empty;
        board[move.obstacleX][move.obstacleY] = Type::obstacle;
    }

    /**
     * 撤销一步棋
     * @param a 要撤销的棋步
     * @param type 当前执子颜色
     */
    inline void unmakeMove(Move a, Type type) {
        board[a.endX][a.endY] = Type::empty;
        board[a.obstacleX][a.obstacleY] = Type::empty;
        // 注意必须最后回复原点状态，否则当 Arrow 发射到原点时将错误。
        board[a.startX][a.startY] = (Type) type;
    }

    /**
     * 获取某方四枚棋子的坐标
     * @param color 棋子颜色
     * @param pos 坐标数组
     */
    void getOwnPosition(const Type &color, Coordinate pos[4]) {
        int cnt = 0;
        for (int i = 0; i < GRIDSIZE; i++)
            for (int j = 0; j < GRIDSIZE; j++)
                if (board[i][j] == color) {
                    pos[cnt].x = i;
                    pos[cnt].y = j;
                    cnt++;
                }
    }

    /**
     * 判断某一步棋是否合法
     * @param move 落子&障碍坐标
     * @param color 当前执子颜色
     * @return 是否合法
     */
    bool checkMove(const Move &move) {
        if (!inMap(move.startX, move.startY)
            || !inMap(move.endX, move.endY)
            || !inMap(move.obstacleX, move.obstacleY))
            return false;
        if (board[move.endX][move.endY] != Type::empty)
            return false;
        if (board[move.obstacleX][move.obstacleY] != Type::empty
            && !(move.obstacleX == move.startX && move.obstacleY == move.startY))
            return false;
        return true;
    }

    /**
     * 判断坐标是否在棋盘内
     * @param x 横坐标
     * @param y 纵坐标
     * @return 是否在棋盘内
     */
    inline bool inMap(int x, int y) const {
        return x >= 0 && x < gridSize
               && y >= 0 && y < gridSize;
    }

private:
    Type board[GRIDSIZE][GRIDSIZE]{};
    int gridSize;
};

/**
 * 按照国际象棋中 King 的走法能走到某个空格的最小移动步数
 * @param board 棋盘
 * @param color 当前执子颜色
 * @param kd 距离数组
 */
void king_move(AmazonsBoard board, Type color, int kd[8][8]) {
    queue<Coordinate> q;    //队列用于广度优先
    Coordinate pos[4];
    board.getOwnPosition(color, pos);
    //初始化kingMove,全都不可到达
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            kd[i][j] = INF_MAX;
        }
    }
    //对每个棋子进行广度优先搜索
    for (auto &po: pos) {
        q.push(po);
        kd[po.x][po.y] = 0;
        while (!q.empty()) {
            Coordinate p = q.front();
            q.pop();
            //八个方向
            for (int j = 0; j < 8; j++) {
                int nx = p.x + dx[j], ny = p.y + dy[j];
                if (board.inMap(nx, ny) && board.at(nx, ny) == Type::empty &&
                    kd[nx][ny] > kd[p.x][p.y] + 1) {
                    q.emplace(nx, ny);
                    kd[nx][ny] = kd[p.x][p.y] + 1;
                }
            }
        }
    }
}

/**
 * 按照国际象棋中 Queen 的走法能走到某个空格的最小移动步数
 * @param board 棋盘
 * @param color 当前执子颜色
 * @param qd 距离数组
 */
void queen_move(AmazonsBoard board, Type color, int qd[8][8]) {
    queue<Coordinate> q;
    //初始化
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            qd[i][j] = INF_MAX;
    Coordinate pos[4];
    board.getOwnPosition(color, pos);
    for (auto &po: pos) {
        q.push(po);
        qd[po.x][po.y] = 0;
        while (!q.empty()) {
            Coordinate p = q.front();
            q.pop();
            //8个方向
            for (int j = 0; j < 8; j++) {
                //移动长度
                for (int step = 1; step < 8; step++) {
                    int nx = p.x + dx[j] * step;
                    int ny = p.y + dy[j] * step;
                    if (board.inMap(nx, ny) && board.at(nx, ny) == Type::empty &&
                        qd[nx][ny] > qd[p.x][p.y] + 1) {
                        q.emplace(nx, ny);
                        qd[nx][ny] = qd[p.x][p.y] + 1;
                    } else
                        break;
                }
            }
        }
    }
}

/**
 * 计算棋子灵活度 mobility（空格通过king走法走一步能到达的空格数(相邻空格数)记为它的灵活度）
 * @param board 棋盘
 * @param color 当前执子颜色
 * @param queenMove_b 黑棋queen的灵活度
 * @param queenMove_w 白棋queen的灵活度
 * @return 棋子灵活度
 */
double get_mobility(AmazonsBoard board, Type color, int queenMove_b[8][8], int queenMove_w[8][8]) {
    //color棋子的灵活度
    double mobility;

    //计算空格灵活度
    int empty_m[8][8];
    memset(empty_m, 0, sizeof(empty_m));
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (board.at(i, j) == Type::empty) {
                for (int m = 0; m < 8; m++) {
                    if (board.inMap(i + dx[m], j + dy[m]) &&
                        board.at(i + dx[m], j + dy[m]) == Type::empty) {
                        empty_m[i][j]++;
                    }
                }
            }
        }
    }

    //棋子的灵活度值取决于它能到达的空格的灵活度值
    Coordinate pos_w[4], pos_b[4];
    board.getOwnPosition(Type::white, pos_w);
    board.getOwnPosition(Type::black, pos_b);
    double result_w = 0, result_b = 0;

    //对于黑子，计算每个黑子的灵活度，求和所能到达的空格的灵活度与距离之比
    for (auto &i: pos_b) {
        for (int j = 1; j < 8; j++) {
            for (int step = 1; step < 8; step++) {
                int nx = i.x + dx[j] * step;
                int ny = i.y + dy[j] * step;
                if (board.inMap(nx, ny) && board.at(nx, ny) == Type::empty &&
                    queenMove_b[nx][ny] != INF_MAX) {       //并且queenMove可到达
                    result_b += (double) empty_m[nx][ny];   //可以尝试除step
                } else break;
            }
        }
    }
    //对于白棋的灵活度
    for (auto &i: pos_w) {
        for (int j = 0; j < 8; j++) {
            for (int step = 1; step < 8; step++) {
                int nx = i.x + dx[j] * step;
                int ny = i.y + dy[j] * step;
                if (board.inMap(nx, ny) && board.at(nx, ny) == Type::empty &&
                    queenMove_w[nx][ny] != INF_MAX) {       //并且queenMove可到达
                    result_w += (double) empty_m[nx][ny];   //同样可以尝试除step
                } else break;
            }
        }
    }

    //计算mobility的最终值
    //使用己方与对方灵活度比值
    //给对方灵活度加0.00001，防止除数为0
    if (color == Type::white) {
        result_b += 0.00001;
        mobility = result_w / result_b;
    } else {
        result_w += 0.00001;
        mobility = result_b / result_w;
    }
    //使用比值而非差值：
    //  1.防止开局灵活度过大
    //  2.在对方被堵死时mobility很大，选择直接这一招直接堵死对方
    return mobility;
}

/**
 * 计算棋子领地评估特征 territory 和棋子位置特征 position
 * @param tq queen领地评估特征
 * @param tk king领地评估特征
 * @param p1 queen位置特征
 * @param p2 king位置特征
 * @param myKingMove 我方kingMove数组，记录king的走法
 * @param yourKingMove 对方kingMove数组，记录king的走法
 * @param myQueenMove 我方queenMove数组，记录queen的走法
 * @param yourQueenMove 对方queenMove数组，记录queen的走法
 */
void get_t_p(double &tq, double &tk, double &p1, double &p2, int myKingMove[8][8],
             int yourKingMove[8][8], int myQueenMove[8][8], int yourQueenMove[8][8]) {
    //假设执黑棋
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            //求tq
            if (myQueenMove[i][j] == yourQueenMove[i][j])
                //距离相同，执棋方有先手优势，+0.5
                tq += 0.3;
            else if (myQueenMove[i][j] == INF_MAX && yourQueenMove[i][j] != INF_MAX)
                //对方可到达，己方无法到达，-3
                tq += -3;
            else if (yourQueenMove[i][j] == INF_MAX && myQueenMove[i][j] != INF_MAX)
                //己方可到达，对方无法到达，+3
                tq += 3;
            else if (yourQueenMove[i][j] > myQueenMove[i][j])
                //都可到达，己方更近，+2
                tq += 2;
            else if (myQueenMove[i][j] > yourQueenMove[i][j])
                //都可到达，对方更近，-2
                tq += -2;

            //求tk，同tq
            if (myKingMove[i][j] == yourKingMove[i][j])
                tk += 0.4;
            else if (myKingMove[i][j] == INF_MAX && yourKingMove[i][j] != INF_MAX)
                tk += -3;
            else if (yourKingMove[i][j] == INF_MAX && myKingMove[i][j] != INF_MAX)
                tk += 3;
            else if (yourKingMove[i][j] > myKingMove[i][j])
                tk += 2;
            else if (myKingMove[i][j] < yourKingMove[i][j])
                tk += -2;

            //求p1、p2
            if (myQueenMove[i][j] == yourQueenMove[i][j]);
            else if (myQueenMove[i][j] == INF_MAX) p1 += 2.0 * (-pow(2.0, -yourQueenMove[i][j]));
            else if (yourQueenMove[i][j] == INF_MAX)p1 += 2.0 * (pow(2.0, -myQueenMove[i][j]));
            else p1 += 2.0 * (pow(2.0, -myQueenMove[i][j]) - pow(2.0, -yourQueenMove[i][j]));
            p2 += min(1.0, max(-1.0, (double) (yourQueenMove[i][j]
                                               - myQueenMove[i][j]) / 6.0));
        }
    }
}

 /**
  * 评估当前棋盘局势
  * @param board 棋盘
  * @param color 被评估方的颜色
  * @param currents 当前步数
  * @param x 一个flag，用于判断是否是第一次调用
  * @return 评估值
  */
double evaluation(AmazonsBoard &board, Type color, int currents, bool x) {
    int king_w[8][8], king_b[8][8];
    int queen_w[8][8], queen_b[8][8];

    //计算kingMove和queenMove
    king_move(board, Type::black, king_b);
    king_move(board, Type::white, king_w);
    queen_move(board, Type::black, queen_b);
    queen_move(board, Type::white, queen_w);

    //计算领地评估特征 territory 和棋子位置特征 position
    double tq = 0, tk = 0, p1 = 0, p2 = 0;
    //假设手持黑棋
    if (color == Type::black)
        get_t_p(tq, tk, p1, p2, king_b, king_w, queen_b, queen_w);
    else
        get_t_p(tq, tk, p1, p2, king_w, king_b, queen_w, queen_b);
    //计算灵活度 mobility
    double mobility = get_mobility(board, color, queen_b, queen_w);

    //计算最终评估值，使用线性加权
    double value;
    if ((turnID + currents) >= 12 || x)
        if ((turnID + currents) >= 12)
            value = 5 * f1[turnID + currents] * tq + f2[turnID + currents] * tk +
                    f3[turnID + currents] * p1 + f4[turnID + currents] * p2 + f5[turnID + currents] * mobility;
        else
            value = 100 * f1[turnID + currents] * tq + 100 * f2[turnID + currents] * tk +
                    1.5 * f3[turnID + currents] * p1 + 1.5 * f4[turnID + currents] * p2 +
                    f5[turnID + currents] * mobility;
    else
        value = f1[turnID + currents] * tq + f2[turnID + currents] * tk + f3[turnID + currents] * p1 +
                f4[turnID + currents] * p2 + 40 * f5[turnID + currents] * mobility -
                evaluation(board, reverseAType(color), currents + 1, false);


    return value;
}

/**
 * 获取最佳走法（核心）
 * @param board 棋盘
 * @param depth 搜索深度
 * @param type 我方执子颜色
 * @param player 1为我方，-1为对方
 * @param d 当前层数
 * @return 最佳走法的评估值
 */
double getBestMove(AmazonsBoard &board, int depth, Type type, int player, int d) {
    //递归深度变成0，对最后一层进行估值
    //时间超过规定时间，对当前层进行估值
    if (depth == 0 || 1000 * (std::clock() - start_time) / CLOCKS_PER_SEC >= max_time) {
        return evaluation(board, type, (d - depth) / 2, true);
    }
    Move moves[3000];
    memset(moves, 0, sizeof(moves));
    Coordinate pos_init[4];
    //四个可用棋子从棋盘获取坐标
    board.getOwnPosition(type, pos_init);

    //生成子节点
    //i为4个可用节点 8为方向 7为一个方向的可以落子的位置
    //每个节点存储可能的落子位置
    int pos = 0;
    //type=reverseAType(type);
    for (auto &i: pos_init) {
        board.at(i.x, i.y) = Type::empty;
        for (int direction = 0; direction < 8; direction++) {
            for (int step = 1; step < 8; step++) {
                int xx = i.x + dx[direction] * step;
                int yy = i.y + dy[direction] * step;
                if (!board.inMap(xx, yy)) break;
                if (board.at(xx, yy) != Type::empty) break;
                for (int _direction = 0; _direction < 8; _direction++) {
                    for (int _step = 1; _step < 8; _step++) {
                        int xxx = xx + dx[_direction] * _step;
                        int yyy = yy + dy[_direction] * _step;
                        if (!board.inMap(xxx, yyy)) break;
                        if (board.at(xxx, yyy) != Type::empty) break;
                        board.at(i.x, i.y) = type;
                        moves[pos].startX = i.x;
                        moves[pos].startY = i.y;
                        moves[pos].endX = xx;
                        moves[pos].endY = yy;
                        moves[pos].obstacleX = xxx;
                        moves[pos].obstacleY = yyy;
                        pos++;
                        board.at(i.x, i.y) = Type::empty;
                    }
                }
            }
        }
        board.at(i.x, i.y) = type;
    }
    //无落点 游戏结束
    if (pos == 0) {
        return evaluation(board, type, (d - depth) / 2, true);
    }
    double values[3000] = {0};
    if (player == 1) {
        for (int i = 0; i < pos; i++) {
            board.makeMove(moves[i], type);
            values[i] = getBestMove(board, depth - 1, reverseAType(type), 0, d);
            board.unmakeMove(moves[i], type);
        }
        double bestValue = -INT_MAX;
        for (int i = 0; i < pos; i++) {
            if (bestValue < values[i]) {
                bestValue = values[i];
            }
        }
        return bestValue;
    } else {
        for (int i = 0; i < pos; i++) {
            board.makeMove(moves[i], type);
            values[i] = getBestMove(board, depth - 1, reverseAType(type), 0, d);
            board.unmakeMove(moves[i], type);
        }
        double bestValue = INT_MAX;
        for (int i = 0; i < pos; i++) {
            if (bestValue > values[i]) {
                bestValue = values[i];
            }
        }
        return bestValue;
    }

}

/**
 * 搜索下一步
 * @param type 执子颜色
 * @param board 棋盘
 * @return 返回下一步走法
 */
Move searchStep(Type type, AmazonsBoard &board) {
    Move moves[3000];
    int pos = 0;
    double value;
    // player = type;
    Coordinate pos_init[4];

    board.getOwnPosition(type, pos_init);
    //int pos = 0;
    for (auto &i: pos_init) {
        board.at(i.x, i.y) = Type::empty;
        for (int direction = 0; direction < 8; direction++) {
            for (int step = 1; step < 8; step++) {
                int xx = i.x + dx[direction] * step;
                int yy = i.y + dy[direction] * step;
                if (!board.inMap(xx, yy)) break;
                if (board.at(xx, yy) != Type::empty) break;
                for (int _direction = 0; _direction < 8; _direction++) {
                    for (int _step = 1; _step < 8; _step++) {
                        int xxx = xx + dx[_direction] * _step;
                        int yyy = yy + dy[_direction] * _step;
                        if (!board.inMap(xxx, yyy)) break;
                        if (board.at(xxx, yyy) != Type::empty) break;
                        board.at(i.x, i.y) = type;
                        moves[pos].startX = i.x;
                        moves[pos].startY = i.y;
                        moves[pos].endX = xx;
                        moves[pos].endY = yy;
                        moves[pos].obstacleX = xxx;
                        moves[pos].obstacleY = yyy;
                        board.makeAMove(moves[pos]);
                        value = evaluation(board, type, 0, true);
                        board.unmakeMove(moves[pos], type);
                        moves[pos].value = (int) value;
                        pos++;
                        board.at(i.x, i.y) = Type::empty;
                    }
                }
            }
        }
        board.at(i.x, i.y) = type;
    }
    std::sort(moves, moves + pos, [](Move a, Move b) { return a.value > b.value; });

    int t, d;
    int player = 0;
    for (d = 1; d < 10; d++) {
        double values[3000] = {0};
        for (t = 0; t < pos; t++) {
            if (1000 * (std::clock() - start_time) / CLOCKS_PER_SEC >= max_time) {
                break;
            }
            board.makeMove(moves[t], type);
            values[t] = getBestMove(board, d, reverseAType(type), player, d);
            //moves[t].value = value;
            board.unmakeMove(moves[t], type);
        }
        if (t == pos - 1) {
            for (int i = 0; i < pos; i++) {
                moves[i].value = (int) values[i];
            }
            std::sort(moves, moves + t, [](Move a, Move b) { return a.value > b.value; });
        }
        if (1000 * (std::clock() - start_time) / CLOCKS_PER_SEC >= max_time) break;
    }

    return moves[0];
    
}

int main() {
    // 初始化棋盘
    AmazonsBoard board;
    Type ownColor = Type::white;    // 默认执白
    cin >> turnID;
    // 分析自己收到的输入和自己过往的输出，并恢复棋盘状态
    // 根据这些输入输出逐渐恢复状态到当前回合
    for (int i = 0; i < turnID; i++) {
        Move move{};
        Type currColor = Type::black;
        // 首先是对手行动（若对方是黑方先手）
        move.input();
        // 第一回合收到坐标是-1, -1，说明我方是黑方（先手）
        // 否则我方是白方，让对方先手
        if (i == 0 && move.startX == -1) {
            ownColor = Type::black;
        } else {
            board.makeAMove(move); // 模拟对方落子
            reverseType(currColor);
        }
        // 然后是本方当时的行动
        // 对手行动总比自己行动多一个
        if (i < turnID - 1) {
            move.input();
            board.makeAMove(move); // 模拟本方落子
            reverseType(currColor);
        }
    }

    // 最后得到最佳落子并输出
    Move resultMove = searchStep(ownColor, board);
    resultMove.print();
    return 0;
}